package sort;

import utils.Common;

import java.util.Random;

/**
 * @author or2
 * @date 2021/7/20 8:51
 */
public class Quick {

    public static final Random RANDOM = new Random();

    public static <E extends Comparable<E>> void sort(E[] arr) {
//        partition1(arr, 0, arr.length - 1);
//        dualPartition2(arr, 0, arr.length - 1);
        partitionTriway(arr, 0, arr.length - 1);
    }

    /**
     * 双路快速排序, 解决算法相同元素下的退化问题
     * @param arr 原数组
     * @param <E> extends Comparable<E>
     */
    public static <E extends Comparable<E>> void dualPartition(E[] arr, int startIndex, int endIndex) {

        if (startIndex >= endIndex) return;
//        if (endIndex - startIndex < 16) {
//            Insert.sort(arr, startIndex, endIndex);
//            return;
//        }

//        在数组完全有序时, 防止算法退化
        int i = RANDOM.nextInt(endIndex - startIndex);
        E beacon = arr[i + startIndex];
        int lIndex = startIndex, rIndex = endIndex;

        while (lIndex < rIndex) {
//            相等时交换, 防止退化 ( 使相等数据均匀分散两边 )
            while (arr[lIndex].compareTo(beacon) < 0 && lIndex < rIndex) {
                lIndex++;
            }
            while (arr[rIndex].compareTo(beacon) > 0 && lIndex < rIndex) {
                rIndex--;
            }
            Common.swapArray(arr, lIndex, rIndex);
//            不要再使 {@code rIndex-- } , 跳跃两个会导致误差, 但无法防止全等数组退化
            lIndex++;
//            记得 >= 0 减小误差且防止 全等数组
            if (rIndex > 0 && arr[rIndex - 1].compareTo(beacon) >= 0) {
                rIndex--;
            }
        }
//        因为保证了 lIndex 的优先级, 最后一定停在大于信标的点
        if (arr[--lIndex].compareTo(beacon) <= 0) {
            dualPartition(arr, startIndex, lIndex);
            dualPartition(arr, lIndex + 1, endIndex);
        } else {
            dualPartition(arr, startIndex, lIndex - 1);
            dualPartition(arr, lIndex, endIndex);
        }

    }

    public static <E extends Comparable<E>> void dualPartition2(E[] arr, int startIndex, int endIndex) {

        if (endIndex - startIndex < 16) {
            Insert.sort(arr, startIndex, endIndex);
            return;
        }

//        在数组完全有序时, 防止算法退化
        int i = RANDOM.nextInt(endIndex - startIndex);
        E beacon = arr[i + startIndex];
        int lIndex = startIndex, rIndex = endIndex;

        while (true) {
//            相等时交换, 防止退化 ( 使相等数据均匀分散两边 )
            while (arr[lIndex].compareTo(beacon) < 0 && lIndex < rIndex) {
                lIndex++;
            }
            while (arr[rIndex].compareTo(beacon) > 0 && lIndex < rIndex) {
                rIndex--;
            }

            if (lIndex >= rIndex) {
                break;
            }

            Common.swapArray(arr, lIndex, rIndex);
//            不要再使 {@code rIndex-- } , 跳跃两个会导致误差, 但无法防止全等数组退化
            lIndex++;
            rIndex--;
        }

//        存在临界问题!!!
        int mid = arr[lIndex].compareTo(beacon) > 0 ? lIndex - 1 : lIndex;
        dualPartition2(arr, startIndex, mid);
        dualPartition2(arr, mid + 1, endIndex);
    }

    /**
     * 三路快速排序
     * @param arr 原数组
     * @param startIndex 排序起始下标
     * @param endIndex 排序终止下标
     * @param <E> extends Comparable<E>
     */
    public static <E extends Comparable<E>> void partitionTriway(E[] arr, int startIndex, int endIndex) {

        if (startIndex >= endIndex) {
            return;
        }
//        if (endIndex - startIndex < 16) {
//            Insert.sort(arr, startIndex, endIndex);
//            return;
//        }

        //        在数组完全有序时, 防止算法退化
        int i = RANDOM.nextInt(endIndex - startIndex);
        E beacon = arr[i + startIndex];
        int lIndex = startIndex, rIndex = endIndex, eqIndex = startIndex;

        while (eqIndex <= rIndex) {

            /**
              {@code arr[startIndex, lIndex), arr[lIndex, eqIndex), arr(rIndex, endIndex] }
             */
            int condition = arr[eqIndex].compareTo(beacon);
            switch (condition) {
                case 0:
                    eqIndex++;
                    break;
                case -1:
                    Common.swapArray(arr, eqIndex, lIndex);
                    lIndex++;
                    eqIndex++;
                    break;
                case 1:
                    Common.swapArray(arr, eqIndex, rIndex);
                    rIndex--;
            }
            /*if (condition == 0) {
                eqIndex++;
            }
            if (condition < 0) {
                lIndex++;
                Common.swapArray(arr, endIndex, lIndex);
                eqIndex++;
            }
            if (condition > 0) {
                Common.swapArray(arr, endIndex, rIndex);
                rIndex--;
            }*/

        }
        partitionTriway(arr, startIndex, lIndex - 1);
        partitionTriway(arr, rIndex + 1, endIndex);
    }

    /**
     * 初版-原地-快速排序
     * @param <E> extends Comparable<E>
     * @param arr 原数组
     * @param startIndex 起始下标
     * @param endIndex 终止下标
     */
    public static <E extends Comparable<E>> void partition(E[] arr, int startIndex, int endIndex) {
        if (startIndex + 16 >= endIndex) {
            Insert.sort(arr, startIndex, endIndex);
            return;
        }

//        在数组完全有序时, 防止算法退化
        int i = RANDOM.nextInt(endIndex - startIndex);
        Common.swapArray(arr, startIndex, i + startIndex);

        int p = startIndex, q = startIndex + 1;
        while (q <= endIndex) {
//            稳定: 否则会出现抖动!
            if (arr[q].compareTo(arr[startIndex]) < 0) {
                p++;
                Common.swapArray(arr, p, q);
            }
            q++;
        }
        Common.swapArray(arr, startIndex, p);

        partition(arr, startIndex, p);
        partition(arr, p + 1, endIndex);
    }
}
